APIO2020练习赛 B题题解

首先祝各位:APIO & NOI RP++!

题目来源:APIO2020练习赛 B (我不知道大家能不能看到这个链接的题目)

题目翻译

  • 这是一道交互题。
  • 有一张二分图,左侧有NN个点,右侧有MM个点。保证NMN\neq M
  • 你可以向交互库提出如下询问:给定一个点集SS,交互库会返回与SS中任意点相邻的所有点。
  • 你需要通过至多QQ次询问,找到一个度数不为11的点。由于NMN\neq M,一定存在这样的点。

数据范围:1N,M50, Q=7, NM1\le N,M\le 50,\ Q=7,\ N\neq M


一道很考察思维和代码细节的题。(反正我被坑了很久)

首先看数据范围,发现Q=7Q=7,大概可以猜到需要O(log(N+M))O(\log (N+M))次查询的算法才能通过。(也可以联想到72=49=5017^2=49=50-1,不过和此题好像没啥联系)

分析这个交互过程:现在假设你询问了一个同属一侧的点集AA,返回的结果是BB。那么:

  • 对于任意xBx\in B都存在一个yAy\in A满足x,yx,y相邻。
  • 对于任意xBx\notin B都不存在一个yAy\in A满足x,yx,y相邻。

乍一看这两句话是废话,就是把询问的方式重新说了一遍。不过我们可以找到一些很好的性质,如果我们现在再查询一下BB呢?假设返回的集合是CC。那么:

  • 如果有一个点xA,xCx\in A,x\notin C。可以断定xx的度数一定为00,否则如果它和yy相连,一定有yBy\in B,那么必然xCx\in C,矛盾。
  • 如果有一个点xA,xCx\notin A,x\in C。一定存在一个yBy\in Bx,yx,y相连,然后一定存在一个zAz\in Ay,zy,z相连。又因为xA,zAx\notin A,z\in Axzx\neq z。那么yy同时与x,zx,z相连,度数至少为22
  • 换句话说,只要此时ACA\neq C,那么我们找到了一个度数不为11的点。

如果我们没找到即A=CA=C,那这个二分图中所有的边要么在ABA∪B里,要么在ABA∪B外。这两部分是不连通的,可以递归处理。我们找到这两部分中满足两侧点数不相等且较小的一部分,递归下去。如果我们选取的AA适当,每次就可以把问题的大小减半,这样就能做到O(log)O(\log)次查询了。

然而这么做的查询次数大概是2log2\log,并不能过题……考虑优化一下。显然你可以选定一个左点集的子集和右点集的子集,把他们放到一起询问,然后你还能很方便地分开交互库返回的结果。然后发现,之前的分析中BCB→C的询问和递归后ABA→B的询问可以合并起来。然后你就糊出了一个复杂度正确但是非常鬼畜的做法。